/**
 *  数组，栈，队列是线性结构类型
 * 树形结构：文件夹目录，DOM结构，路由配置，ast语法树...
 *  根节点，子节点
 *  子树
 * 叶子节点：没有儿子节点的
 *
 * 二叉搜索树（二叉排序树）：按照规则来存放的，以一个根为准，比这个根大的放右边，比小的放左边
 *  循环查找传入节点的parent, 然后跟子节点比较，小的放左边，大的放右边
 *
 */

class Node {
  // 节点之间必须有个parent属性

  constructor(element, parent) {
    this.element = element;
    this.parent = parent; // 记录当前的节点的父节点是谁
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null; // 树根
    this.size = 0;
  }
  add(element) {
    if (this.root == null) {
      // 第一个数据当做根
      this.root = new Node(element, null);
      this.size++;
      return;
    }
    // 根据条件不停的找，找到节点为空时，将上一次的值保存起来，将节点插入到保存的节点中

    let currentNode = this.root;
    let parent = null,
      compare = null;
    while (currentNode) {
      compare = element - currentNode.element;
      // 先存起来，再进入子树之前
      parent = currentNode;
      if (compare > 0) {
        currentNode = currentNode.right;
      } else {
        currentNode = currentNode.left;
      }
    }
    let newNode = new Node(element, parent);
    if (compare > 0) {
      parent.right = newNode;
    } else {
      parent.left = newNode;
    }
    this.size++;
  }
  // 树的遍历方式
  // 前序遍历
  preorderTraversal(visitor) {
    const traversal = (node) => {
      if (node == null) return;
      visitor.visit(node);
      // console.log(node.element);
      traversal(node.left);
      traversal(node.right);
    };
    traversal(this.root);
  }
  // 中序遍历
  inorderTraversal(visitor) {
    const traversal = (node) => {
      if (node == null) return;
      traversal(node.left);
      // console.log(node);
      visitor.visit(node);
      traversal(node.right);
    };
    traversal(this.root);
  }
  // 后序遍历
  postorderTraversal(visitor) {
    const traversal = (node) => {
      if (node == null) return;
      traversal(node.left);
      traversal(node.right);
      // console.log(node);
      visitor.visit(node);
    };
    traversal(this.root);
  }
  // 层序遍历
  levelorderTraversal(visitor) {
    if (this.root == null) return;
    let stack = [this.root]; // 10

    let index = 0,
      currentNode = null;
    while ((currentNode = stack[index++])) {
      visitor.visit(currentNode);
      if (currentNode.left) {
        stack.push(currentNode.left);
      }
      if (currentNode.right) {
        stack.push(currentNode.right);
      }
    }
  }

  // 翻转二叉树：左右互换
  invertTree() {
    if (this.root == null) return;
    let stack = [this.root]; // 10

    let index = 0,
      currentNode = null;
    while ((currentNode = stack[index++])) {
      let temp = currentNode.left;
      currentNode.left = currentNode.right;
      currentNode.right = temp;
      if (currentNode.left) {
        stack.push(currentNode.left);
      }
      if (currentNode.right) {
        stack.push(currentNode.right);
      }
    }
  }
}

let bst = new BST();
// 二叉搜索树种的内容必须是可比较性的
// let arr = [10, 8, 19, 6, 15, 22, 20];
let arr = [28, 15, 42, 18, 22, 5, 40];
// 生成二叉树
arr.forEach((r) => {
  bst.add(r);
});

// console.dir(bst, { depth: 10 });
// 访问者模式，
// bst.preorderTraversal();
bst.postorderTraversal({
  visit(node) {
    console.log(node.element);
  },
});

// bst.levelorderTraversal({
//   visit(node) {
//     console.log(node.element, '+++++');
//   },
// });

// bst.invertTree();
// console.log(bst.root);

// console.dir(bst, { depth: 10 });

/**
 * 常见的遍历树：
 *   1. 前序遍历，父->左->右
 *   2. 中序遍历：左->父->右
 *   3. 层续遍历：一层一层从上往下
 *   4. 后续遍历：左->右->父
 * 尾递归？
 *  二叉树翻转？左右互换，树的遍历
 */
